<?php
/**
 * Finding the lowest common ancestor of two nodes in a binary tree
 * 2 algorithms covered by leetcode
 */

require_once 'util.php';

importJS();

$arr = generateRandomArray(0, 99, 10);

$value1 = $arr[3];
$value2 = $arr[5];

var_dump($arr);

$root = null;
foreach( $arr as $value ){
	$root = bt_insert($value, $root);
}

bt_print_inorder($root);
bt_draw($root);

$lca = bt_lowest_common_ancestor2($root, $value1, $value2);

echo "<br/>";

echo "{$lca->value} is LCA for $value1 and $value2";

/*
 * Algo 1: in a top down traverse:
 * 1) if two nodes lies in the left sub tree, continue on the left sub tree
 * 2) if two nodes lies in the right sub tree, continue on the right sub tree
 * 3) if two nodes lays as each on both side, this should be the LCA
 * 4) if current node is one of the nodes, this is the LCA
 *
 * Since every node will be traversed at every node for the counting, the complexity is O(n^2)
 */
function bt_lowest_common_ancestor( $root, $value1, $value2 ){

	if( $root->value == $value1 || $root->value == $value2 ){
		return $root;
	}

	$leftMatches = bt_count_matches( $root->left, $value1, $value2 );
	if( 2 <= $leftMatches ){
		return bt_lowest_common_ancestor($root->left, $value1, $value2);
	}
	else if( 1 == $leftMatches ){
		return $root;
	}
	else if( 0 == $leftMatches ){
		return bt_lowest_common_ancestor($root->right, $value1, $value2);
	}
}

/**
 * Traversse a binary tree to count the number of matches
 * @param unknown_type $root
 * @param unknown_type $value
 */
function bt_count_matches( $root, $value1, $value2 ){
	if( !$root ){
		return 0;
	}
	$match = ($root->value == $value1 || $root->value == $value2)?1:0;
	return $match + bt_count_matches($root->left, $value1, $value2) + bt_count_matches($root->right, $value1, $value2);
}

/*
 * Algo 2: in a bottom up traverse:
 * 1) returns itself if is a match with one of the values
 * 2) returns itself if there is result on both child directions
 * 3) return child result where not null
 *
 * O(n) solution but a bit tricky to understand...
 */
function bt_lowest_common_ancestor2($root, $value1, $value2){
	if( !$root ){
		return null;
	}

	if( $root->value == $value1 || $root->value == $value2 ){
		return $root;
	}

	$lresult = bt_lowest_common_ancestor2($root->left, $value1, $value2);
	$rresult = bt_lowest_common_ancestor2($root->right, $value1, $value2);

	if( $lresult && $rresult ){
		return $root;
	}
	else if( $lresult ){
		return $lresult;
	}
	else {
		return $rresult;
	}

}